/*
 * @Author: sympsel sympsel@outlook.com
 * @Date: 2025-07-21 12:25:28
 * @LastEditors: sympsel sympsel@outlook.com
 * @LastEditTime: 2025-07-21 12:36:38
 * @FilePath: \work25_7_20\src\BinaryTree.h
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

#ifndef MALLOC
#define MALLOC(_type_, _count_) (_type_*)malloc(sizeof(_type_) * (_count_))
#endif

typedef int BTDataType;

typedef struct TreeNode {
    BTDataType val;
    struct TreeNode* left;
    struct TreeNode* right;
    /* data */
}TreeNode;

TreeNode* TreeNodeCreate(BTDataType val);

bool TreeEmpty(TreeNode* root);

bool IsLeaf(TreeNode* root);

// 二叉树销毁
void TreeDestory(TreeNode* root);
// 二叉树节点个数
int TreeSize(TreeNode* root);
// 二叉树叶子节点个数
int TreeLeafSize(TreeNode* root);
// 二叉树第k层节点个数
int TreeLevelKSize(TreeNode* root, int k);
// 二叉树查找值为x的节点
TreeNode* TreeFind(TreeNode* root, BTDataType x);
// 二叉树前序遍历 
void PreOrder(TreeNode* root);
// 二叉树中序遍历
void InOrder(TreeNode* root);
// 二叉树后序遍历
void PostOrder(TreeNode* root);
// 层序遍历
void LevelOrder(TreeNode* root);

void TreeShow(TreeNode* root, void (*show)(TreeNode*));

// 判断二叉树是否是完全二叉树
bool TreeCompleteBFS(TreeNode* root);

bool TreeCompleteDFS(TreeNode* root);